package 每日一题;

public class No1423可获得的最大点数 {

    /**
     * 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
     * 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
     * 你的点数就是你拿到手中的所有卡牌的点数之和。
     * 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
     *
     * 示例 1：
     * 输入：cardPoints = [1,2,3,4,5,6,1], k = 3
     * 输出：12
     * 解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。
     * 最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
     * 示例 2：
     * 输入：cardPoints = [2,2,2], k = 2
     * 输出：4
     * 解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
     * 示例 3：
     * 输入：cardPoints = [9,7,7,9,7,7,9], k = 7
     * 输出：55
     * 解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
     * 示例 4：
     * 输入：cardPoints = [1,1000,1], k = 1
     * 输出：1
     * 解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
     * 示例 5：
     * 输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
     * 输出：202
     */

    private int[] arr;
    private Integer[][][][] memo;

    public int maxScoreBad(int[] cardPoints, int k) {
        //先暴力递归
        this.arr=cardPoints;
        memo=new Integer[k+1][this.arr.length+2][this.arr.length+2][2];
        return dg(k,0,arr.length-1);
    }

    //超时,超空间解法: 备忘录
    private int dg(int count,int left,int right){
        //题目已经保证,1<=k<length
        if(count==0){
            return 0;
        }

        System.out.println("边:"+(count-1)+"-"+(left+1)+"-"+right);
        //选左边
        if(memo[count - 1][left + 1][right][0]==null) {
            int leftSum = dg(count - 1, left + 1, right) + arr[left];
            memo[count - 1][left + 1][right][0] = leftSum;
        }

        System.out.println("边:"+(count-1)+"-"+(left)+"-"+(right-1));
        //选右边
        if(memo[count - 1][left][right - 1 + 1][1]==null) {
            int rightSum = dg(count - 1, left, right - 1) + arr[right];
            memo[count - 1][left][right - 1 + 1][1] = rightSum;
        }

        return Math.max(memo[count-1][left+1][right][0],memo[count-1][left][right-1+1][1]);
    }

    /**
     * 参照解法:
     * 每次都只能从一边取,外界窗口;
     * 边边两端与虚无区域形成一个窗口
     */
    public int maxScoreGood(int[] cardPoints,int k){

        int left=0;
        int right=k-1;
        //整体向左移动,直至 left=length-k,right=0;
        int sum=0;
        int max=0;

        //base
        for (int i = 0; i < k; i++) {
            sum+=cardPoints[i];
        }
        max=sum;

        //最多向左移动k次
        for (int i = 1; i <= k; i++) {
            if(right>=0) {
                sum -= cardPoints[right];
                right -= 1;
            }
            left=cardPoints.length-i;
            sum+=cardPoints[left];
            max=Math.max(max,sum);
        }

        return max;
    }

    public static void main(String[] args) {
        No1423可获得的最大点数 n=new No1423可获得的最大点数();
        int[] arr={4,6,9,4,3,20,2,1};
        int result = n.maxScoreGood(arr, 5);
        System.out.println(result);
    }

}
